package random_test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test_10_9 {

    //1089. 复写零
    public void duplicateZeros(int[] arr) {
        // 1. 找到最后一个复写的数
        // 定义两个指针 cur和dest, 当cur遇到 0 dest+2, 其他情况cur和dest同时+1
        int cur = 0, dest = -1;
        while(dest < arr.length - 1) {
            if(arr[cur] == 0) {
                dest += 2;
            } else {
                dest++;
            }
            if(dest >= arr.length - 1) break;
            cur++;
        }
        // 2. 处理dest的边界情况
        if(dest == arr.length) {
            arr[--dest] = 0;
            dest--;
            cur--;
        }
        // 3. 从后向前完成复写操作
        for(; dest >= 0; cur--,dest--) {
            if(arr[cur] == 0) arr[dest--] = arr[cur];
            arr[dest] = arr[cur];
        }
    }


    //202. 快乐数
    public boolean isHappy(int n) {
        int fast = convert(n);
        int slow = n;
        while(fast != slow) {
            slow = convert(slow);
            fast = convert(fast);
            fast = convert(fast);
        }
        if(fast == 1) return true;
        return false;
    }
    private int convert(int n) {
        int sum = 0;
        while(n > 0) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }


    //11. 盛最多水的容器
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, max = 0;
        int v = 0;
        while(left < right) {
            int h = Math.min(height[left], height[right]);
            v = (right - left) * h;
            if(v > max) max = v;
            if(height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }


    //611. 有效三角形的个数
    public int triangleNumber(int[] nums) {
        if(nums.length < 3) return 0;

        Arrays.sort(nums);
        int i = nums.length - 1, sum = 0;
        while(i >= 2) {
            int left = 0;
            int right = i - 1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]) {
                    sum += right - left;
                    right--;
                } else {
                    left++;
                }
            }
            i--;
        }
        return sum;
    }


    //15. 三数之和
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0; i < nums.length - 2; i++) {
            // 当 nums[i] > 0，则 i 后面的元素相加一定 > 0
            if(nums[i] > 0) break;
            // 跳过重复的 nums[i]
            while(i > 0 && i < nums.length && nums[i] == nums[i-1]) i++;
            if(i == nums.length) break;
            int sum = -nums[i];
            int left = i + 1, right = nums.length - 1;
            while(left < right) {
                if(nums[left] + nums[right] == sum) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left++]);
                    list.add(nums[right--]);
                    ret.add(list);
                    // 跳过重复的 left 和 right
                    while(left < right && nums[left] == nums[left-1]) left++;
                    while(left < right && nums[right] == nums[right+1]) right--;
                } else if(nums[left] + nums[right] > sum) {
                    right--;
                } else {
                    left++;
                }
            }
        }
        return ret;
    }
}

